package com.leetcode.剑指offer第2版;

/**
 * @author 覃国强
 * @date 2022-05-13 18:45
 */
public class 剑指Offer_51_数组中的逆序对 {

  static
  class Solution {
    public int reversePairs(int[] nums) {
      if (nums == null || nums.length == 0) {
        return 0;
      }
      return mergeSort(nums, 0, nums.length - 1, new int[nums.length]);
    }

    private int mergeSort(int[] nums, int start, int end, int[] temp) {
      if (start < end) {
        int mid = (start + end) / 2;
        int leftAnswer = mergeSort(nums, start, mid, temp);
        int rightAnswer = mergeSort(nums, mid + 1, end, temp);
        int curAnswer = merge(nums, start, mid, end, temp);
        return leftAnswer + rightAnswer + curAnswer;
      }
      return 0;
    }

    private int merge(int[] nums, int start, int mid, int end, int[] temp) {
      int left = start;
      int right = mid + 1;
      int index = start;
      int answer = 0;
      while (left <= mid && right <= end) {
        if (nums[left] <= nums[right]) {
          temp[index++] = nums[left++];
        } else {
          temp[index++] = nums[right++];
          answer += (mid - left + 1);
        }
      }
      while (left <= mid) {
        temp[index++] = nums[left++];
      }
      while (right <= end) {
        temp[index++] = nums[right++];
      }
      for (int i = start; i <= end; ++i) {
        nums[i] = temp[i];
      }

      return answer;
    }

  }

}
